class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        
        def getTrees(start, end):  
            if start > end:
                return [None]
            
            ans = []
            for i in range(start, end+1):
                left_tree = getTrees(start, i - 1)
                right_tree = getTrees(i + 1, end)
                for l in left_tree:
                    for r in right_tree:
                        head = TreeNode(i)
                        head.left = l
                        head.right = r
                        ans.append(head)
            return ans
        return getTrees(1, n)
